package main

import "fmt"

//小孩的结构体
type Boy struct {
	no   int
	next *Boy
}

//num:表示小孩的个数
//boy:返回该环形的链表的第一个小孩的指针
func AddBoy(num int) *Boy {
	first := &Boy{}
	curBoy := &Boy{}
	if num < 1 {
		fmt.Println("num的值不对")
		return first
	}
	//循环构建环形链表
	for i := 1; i <= num; i++ {
		boy := &Boy{
			no: i,
		}
		//分析构成循环链表，需要一个辅助指针
		if i == 1 { //第一个小孩
			first = boy
			curBoy = boy
			curBoy.next = first
		} else {
			curBoy.next = boy
			curBoy = boy
			curBoy.next = first
		}
	}
	return first
}

func ShowBoy(first *Boy) {
	//处理空的环形链表
	if first.next == nil {
		fmt.Println("链表为空，没有小孩")
		return
	}

	//创建一个指针，帮助遍历
	curBoy := first
	for {
		fmt.Println("id=", curBoy.no)
		if curBoy.next == first {
			break
		}
		curBoy = curBoy.next
	}
}

//分析思路
/*
	设置编号为1，2，。。。n个人围坐一圈，约定编号为k的人从
1开始报数，数到m的那个人出列，他的下一位又从1开始报数，数到m的那个人出列，
以此类推，直到所有人都出列为止，由此产生一个出队编号的序列
*/
func PlayGame(first *Boy, startNo int, countNum int) {
	//1、空的链表我们单独处理
	if first.next == nil {
		fmt.Println("空的链表，没有小孩")
		return
	}
	//留一个，判断startNo<=小孩的总数
	//2、需要定义辅助指针，帮助我们删除小孩
	tail := first
	//3、让tail指向环形链表的最后一个小孩
	for {
		//说明tail到了最后一个小孩
		if tail.next == first {
			break
		}
		tail = tail.next
	}
	//4、让first移动到startNo
	for i := 1; i <= startNo-1; i++ {
		first = first.next
		tail = tail.next
	}
	//5、开始数countNum，然后就删除first指向的小孩
	for {
		//开始数countNum-1次
		for i := 1; i <= countNum-i; i++ {
			first = first.next
			tail = tail.next
		}
		fmt.Printf("小孩为%d,出圈-》\n", first.no)
		first = first.next
		tail.next = first
		//判断tail==first,圈中只有一个小孩
		if tail == first {
			break
		}
	}
	fmt.Printf("小孩编号为%d出圈\n", first.no)
}

func main() {
	boy := AddBoy(500)
	ShowBoy(boy)
	PlayGame(boy, 20, 31)
}
